/**
 * 给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素，并返回移除后数组的新长度。
 * 不要使用额外的数组空间，你必须仅使用 O(1) 额外空间并原地修改输入数组。
 */

//时间复杂度：O(n)
//空间复杂度：O(1)
var removeElement = (nums, val) => {
  let k = 0;
  for (let i = 0; i < nums.length; i++) {
    if (nums[i] != val) {
      nums[k++] = nums[i]
    }
  }
  return k;
};

// 时间复杂度：O(n^2)
// 空间复杂度：O(1)
var removeElement = (nums, val) => {
  let k = nums.length;
  for (let i = 0; i < k; i++) {
    if (nums[i] == val) { // 发现需要移除的元素，就将数组集体向前移动一位
      for (let j = i + 1; j < k; j++) {
        nums[j - 1] = nums[j];
      }
      i--; // 因为下标i以后的数值都向前移动了一位，所以i也向前移动一位
      k--; // 此时数组的大小-1
    }
  }
  return k;
};

console.log(removeElement([3, 2, 2, 3], 3)); // 2